package top.truism.stack;

import java.util.Stack;

/**
 * 汉诺塔问题的栈实现
 */
public class HanoiProblemByStack {

    public static int hanoi(int num, String left, String mid, String right) {
        Stack<Integer> lS = new Stack<>();
        Stack<Integer> mS = new Stack<>();
        Stack<Integer> rS = new Stack<>();
        lS.push(Integer.MAX_VALUE);
        mS.push(Integer.MAX_VALUE);
        rS.push(Integer.MAX_VALUE);
        for (int i = num; i > 0; i--) {
            lS.push(i);
        }
        Action[] record = {Action.NO};
        int step = 0;
        while (rS.size() != num + 1) {
            // 第一步一定是从 Left 到 Right
            step += fStackToTStack(record, Action.MToL, Action.LToM, lS, mS, left, mid);
            step += fStackToTStack(record, Action.LToM, Action.MToL, mS, lS, mid, left);
            step += fStackToTStack(record, Action.RToM, Action.MToR, mS, rS, mid, right);
            step += fStackToTStack(record, Action.MToR, Action.RToM, rS, mS, right, mid);
        }
        return step;
    }

    private static int fStackToTStack(Action[] record, Action preAct, Action curAct,
                                      Stack<Integer> fStack, Stack<Integer> tStack,
                                      String from, String to) {
        // 大数不能压住小数, 且不会逆行操作，否则就不是最优步法
        if (record[0] != preAct && fStack.peek() < tStack.peek()) {
            tStack.push(fStack.pop());
            print(tStack.peek(), from, to);
            record[0] = curAct;
            return 1;
        }
        return 0;
    }

    private static void print(int num, String from, String to) {
        System.out.println("Move " + num + " from " + from + " to " + to);
    }

    /**
     * 元素移动的操作类型
     */
    enum Action {
        NO,
        LToM,
        MToL,
        RToM,
        MToR
    }

}
